package com.cn.algorithm.two.union.test;

import com.cn.algorithm.two.union.GenericUnionFind;
import com.cn.algorithm.two.union.domain.Student;

import java.util.HashMap;
import java.util.Objects;

public class GenericUnionFindJ<V> {

    public HashMap<V,Node<V>> map = new HashMap<>();

    public void put(V value) {
        if (map.containsKey(value)) {
            return;
        }
        map.put(value, new Node<>(value));
    }

    public V find(V value) {
        if (value == null) {
            throw new NullPointerException();
        }
        Node<V> node = node(value);
        return node == null ? null : node.value;
    }

    public Node<V> node(V value) {
        Node<V> node = map.get(value);
        if (node == null) {
            return null;
        }
        while (!Objects.equals(node.value, node.parent.value)) {
            node.parent = node.parent.parent;
            node = node.parent;
        }
        return node;
    }

    public boolean isSame(V v1, V v2) {
        return Objects.equals(node(v1), node(v2));
    }

    public void union(V v1, V v2) {
        Node<V> node1 = node(v1);
        if (node1 == null) {
            return;
        }
        Node<V> node2 = node(v2);
        if (node2 == null || Objects.equals(node1, node2)) {
            return;
        }
        if (node1.rank > node2.rank) {
            node2.parent = node1;
        } else if (node1.rank < node2.rank) {
            node1.parent = node2;
        } else {
            node1.parent = node2;
            node2.rank++;
        }
    }




    public static class Node<V> {

        int rank = 1;

        Node<V> parent = this;

        V value;

        public Node(V value) {
            this.value = value;
        }
    }

    public static void main(String[] args) {
        GenericUnionFindJ<Student> uf = new GenericUnionFindJ<>();
        Student stu1 = new Student(1, "jack");
        Student stu2 = new Student(2, "rose");
        Student stu3 = new Student(3, "jack");
        Student stu4 = new Student(4, "rose");
        uf.put(stu1);
        uf.put(stu2);
        uf.put(stu3);
        uf.put(stu4);

        uf.union(stu1, stu2);
        uf.union(stu3, stu4);

        System.out.println(uf.isSame(stu2, stu3));
        System.out.println(uf.isSame(stu3, stu4));
        System.out.println(uf.isSame(stu1, stu3));
        System.out.println(uf.isSame(stu1, stu2));
    }
}
